package com.pan.alg.leecode;

import java.util.List;

/**
 *
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/triangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author by panstark
 * @description
 * @notice
 * @date 2021/8/4
 */
public class Leecode120 {
    public int shortest1(List<List<Integer>> triangle ){
        int n = triangle.size();
        //建立一个结果数组
        int[][] sum = new int[n][n];
        //获取数组第一个值
        sum[0][0]=triangle.get(0).get(0);
        //求出所有的可能的求和
        for (int i = 1; i < triangle.size(); i++) {
            //如果是左侧边缘的值，根据规则只可能是左上侧累加下来的
            sum[i][0]=sum[i-1][0]+triangle.get(i).get(0);
            List<Integer> rows = triangle.get(i);
            for (int j = 1; j < i; j++) {
                //如果是中间范围的值，则当前值的结果只可能是上面紧挨着的两个结果与当前坐标值的求和
              sum[i][j]=Math.min(sum[i-1][j],sum[i-1][j-1])+triangle.get(i).get(j);
            }
            //如果是右侧边缘的值，根据规则只可能是右侧累加下来的值
            sum[i][i]=sum[i-1][i-1]+triangle.get(i).get(i);
        }
        //走完以上的计算逻辑，我们就拥有了一个全量的结果集，每一行每一个位置最小的求和值都是有的
        //从最后一行的和中找出最小的
        int sumStandard = sum[n][0];
        for (int i = 1; i <n ; i++) {
            sumStandard = Math.min(sumStandard,sum[n][i]);
        }
        return sumStandard;
    }
}
